A b-tree is a type of data structure used to quickly locate files (called keys) in a database. B-trees are usually used in parallel with databases because they generally only hold key values. Each node of a b-tree may have a variable number of keys and children. The keys are stored in increasing order. Each key has an associated child that is the root of a subtree containing all nodes with keys less than or equal to the key but greater than the preceding key. A node also has an additional rightmost child that is the root for a subtree containing all keys greater than any keys in the node. This property allows users to quickly locate a particular key. Once the desired key is located in the b-tree, the key can then be used to quickly retrieve the rest of the record that the user may desire to locate from a database. It is also common to have a number of b-trees used to index the same set of records. For example, a user of a contacts database may have a b-tree containing keys corresponding to first names, and another corresponding to last names, allowing the fast retrieval of records using first names or last names.
Given the fact that generating a b-tree from the set of records is not practical for a large number of records (e.g., because of time and memory space considerations), they are persisted together with the records in the database persistent storage, so their size contributes to the end database size. The size required to store a database is important even with the progress made in terms of storage media capabilities. The database may have to be used on a device with less capabilities (e.g., PDAs, cell phones, embedded devices) or it may have to be backed up frequently. Also, a larger persisted database size will likely lead to a poor overall performance, as more I/O has to be done.
The recent development in the smart devices market created a demand for small, reliable and fast database engines, as a common usage for those devices is to support a ‘mobile’ data storage. This storage may include data such as contacts and email or fairly large databases of business data.
Database size is more critical with these devices, as they usually provide limited storage capabilities. At the same time, storing database files on relatively slow storage like flash memory puts more pressure on minimizing the number of I/O, and this makes a good storage approach critical for a database engine in this market.
In view of the foregoing, there is a need for fast, efficient, and reliable systems and methods for minimizing the size of a b-tree.